#include <iostream>
#include <queue>
#include <string>
using namespace std;

#include <ctime>
#include <cstdlib>

namespace FangZhang // 命名空间封装一下
{
    // 进程PCB
    class PCB
    {
    public:
        PCB(int id = -1, int priority = -1, int cpuTime = -1, int allTime = -1, const string& state = "")
            : _id(id)
            , _priority(priority)
            , _cpuTime(cpuTime)
            , _allTime(allTime)
            , _state(state)
        {}

        int SubPriority(int i = 3)                  // 优先级 - 3
        {
            return _priority -= i;
        }

        int PlusCputime(int i = 1)                   // 时间片 + 1
        {
            return _cpuTime += i;
        }

        int SubAlltime(int i = 1)                   // 还需时间片 - 1
        {
            return _allTime -= i;
        }

    public:
        int _id;                                 // 进程标识数
        int _priority;                           // 进程优先数
        int _cpuTime;                            // 进程已占用时间片
        int _allTime;                            // 进程还需时间片
        string _state;                           // 进程状态
    };

    // 仿函数，通过优先级对比来构建大堆
    class less
    {
    public:
        bool operator()(const PCB& son, const PCB& father)
        {
            return son._priority < father._priority;
        }
    };

    // 堆实现，每次都能找出优先级最大的PCB
    class DispatchQueue
    {
    public:
        DispatchQueue(int size = 10)
        {
            // 创建进程
            for(int i = 0; i < size; ++i)
            {
                int priority = random() % 30 + 5;
                int allTime = random() % 20 + 3;
                pq.push(PCB(i, priority, 0, allTime, "ready"));
                PCBs.push_back(PCB(i, priority, 0, allTime, "ready"));
            }
        }

        // 显示所有进程状态
        void ShowProcess()
        {
            cout << "_______________________________________________________________" << endl;
            cout << "ID\t\tPRIOPRITY\t\tCPUTIME\t\tALLTIME\t\tSTATE" << endl;
            
            for(auto &e : PCBs)
            {
                cout << e._id << "\t\t" << e._priority << "\t\t\t" << e._cpuTime << "\t\t" << e._allTime << "\t\t" << e._state << endl;
            }
            
            cout << "_______________________________________________________________" << endl << endl;
        }

        // 调度
        void Dispatch()
        {
            cout << "当前各个进程初始状态为:" << endl;
            ShowProcess(); 

            // 周转时间
            double curTime = 0;
            double time = 0;

            // 开始调度
            while(!pq.empty())
            {
                // 获取堆顶，即优先级最高的进程
                PCB top = pq.top();
                pq.pop();
                cout << "当前调度" << top._id << "号进程, 其优先级为" << top._priority << ", 调度后各个进程的状态如下:" << endl;
                if(top._allTime >= 3) // 剩余时间片大于3，就正常调度
                {
                    ++curTime;
                    top.SubAlltime();
                    top.SubPriority();
                    top.PlusCputime();
                    pq.push(top);
                }
                else if(top._allTime < 3 && top._allTime > 0)// 剩余时间片小于3但仍大于零，分情况讨论
                {
                    // 正常调度
                    top.SubAlltime();
                    top.SubPriority();
                    top.PlusCputime();      
                    
                    if(top._allTime > 0)
                    {
                        // 剩余时间片还是大于0的，继续调度
                        ++curTime;
                        pq.push(top);
                    }
                    else
                    {
                        // 剩余时间片等于0的，调度结束，无需再次入堆
                        time += curTime;
                        cout << "#####" << top._id << "号进程运行结束" << endl;
                        PCBs[top._id]._state = "over";
                    }
                }

                // 剩余时间片大于0的，更新一下表中各个字段的数值
                PCBs[top._id]._allTime = top._allTime;
                PCBs[top._id]._cpuTime = top._cpuTime;
                PCBs[top._id]._priority = top._priority;

                // 显示一下所有PCB的状态
                ShowProcess();
            }

            cout << "平均周转时间::" << time / PCBs.size() << endl;
        }

    private:
        priority_queue<PCB, vector<PCB>, less> pq;// 优先级队列，即堆
        vector<PCB> PCBs; // 用来打印PCB状态的
    };
}